BZOJ1071【SCOI2007】组队 <双指针>

Problem

【SCOI2007】组队

Description

每年都有球员选秀环节。通常用速度和身高两项数据来衡量一个篮球运动员的基本素质。假如一支球队里速度最慢的球员速度为，身高最矮的球员高度为，那么这支球队的所有队员都应该满足：。其中和为给定的经验值。这个式子很容易理解，如果一个球队的球员速度和身高差距太大，会造成配合的不协调。请问作为球队管理层的你，在名选秀球员中，最多能有多少名符合条件的候选球员。

Input

第一行四个数。
下接行每行两个数描述一个球员的和。

Output

最多候选球员数目。

Sample Input

Sample Output

HINT

，和不大于。在长整型以内。
数据加强，程序未重测。

标签：双指针

Solution

挺神的题，两个序列上双指针的操作挺奇葩。

对于每个队员，令，将队员数组同时复制到中，分别排序。按照从小到大排序，按照从小到大排序。
首先按任意顺序枚举的最小值大小，不妨直接再中枚举。这时定义左指针和右指针和，只是与普通双指针不同的是，指向的是中的元素，指向的是中的元素，可以理解为中的右指针是不动的，中的左指针是不动的。这样精妙设计是考虑到中递增的值如果不满足要求，即小于枚举到的值，小于的部分一定是从前面开始的；同样地，中递增的值如果不满足要求，即大于，大于的部分一定是从后面开始的。这样对每个数组跑“单指针”即可得到可行最大子段，更新答案即可。

Code

#include <bits/stdc++.h>
#define MAX_N 5000
using namespace std;
typedef long long lnt;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n;	lnt A, B, C, miv, mxv;
struct node {lnt h, v, s;} p[MAX_N+5], q[MAX_N+5];
bool cmph(const node &a, const node &b) {return a.h <= b.h;}
bool cmps(const node &a, const node &b) {return a.s <= b.s;}
int main() {
    read(n), read(A), read(B), read(C);	int ans = 0;
    for (int i = 1; i <= n; i++) read(p[i].h), read(p[i].v);
    for (int i = 1; i <= n; i++) p[i].s = A*p[i].h+B*p[i].v, q[i] = p[i];
    sort(p+1, p+n+1, cmph), sort(q+1, q+n+1, cmps);
    for (int i = 1, l, r, cnt; i <= n; i++) {
        l = r = cnt = 0, miv = p[i].v, mxv = miv+C/B;
        for (int j = 1; j <= n; j++, ans = max(ans, cnt)) {
            while (r < n && q[r+1].s <= A*p[j].h+B*p[i].v+C)
                r++, cnt += q[r].v >= miv && q[r].v <= mxv;
            while (l < n && p[l+1].h < p[j].h)
                l++, cnt -= p[l].v >= miv && p[l].v <= mxv;
        }
    }
    return printf("%d\n", ans), 0;
}